\documentclass[a4paper]{article} 

\usepackage{listings}
\lstset{tabsize=4, %
	frame=shadowbox, %把代码用带有阴影的框圈起来
	commentstyle=\color{red!50!green!50!blue!50},%浅灰色的注释
	rulesepcolor=\color{red!20!green!20!blue!20},%代码块边框为淡青色
	keywordstyle=\color{blue!90}\bfseries, %代码关键字的颜色为蓝色，粗体
	showstringspaces=false,%不显示代码字符串中间的空格标记
	stringstyle=\ttfamily, % 代码字符串的特殊格式
	keepspaces=true, %
	breakindent=22pt, %
	numbers=left,%左侧显示行号
	stepnumber=1,%
	numberstyle=\tiny, %行号字体用小号
	basicstyle=\footnotesize, %
	showspaces=false, %
	flexiblecolumns=true, %
	breaklines=true, %对过长的代码自动换行
	breakautoindent=true,%
	breakindent=4em, %
	%escapebegin=\begin{CJK*}{GBK}{hei},escapeend=\end{CJK*},
	aboveskip=1em, %代码块边框
	fontadjust,
	captionpos=t,
	framextopmargin=2pt,framexbottommargin=2pt,
	abovecaptionskip=-3pt,belowcaptionskip=3pt,
	xleftmargin=4em,xrightmargin=4em, % 设定listing左右的空白
	texcl=true,
	% 设定中文冲突，断行，列模式，数学环境输入，listing数字的样式
	extendedchars=false,columns=flexible,mathescape=true
	% numbersep=-1em
}
\usepackage{cite}
\usepackage{fancyhdr}
\usepackage{lipsum}
\usepackage{extarrows}
\usepackage{ctex}
\usepackage{amsfonts,amssymb} 
\usepackage{amsmath} 
\usepackage{cases}
\usepackage{geometry}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{framed}
\usepackage{float}
\usepackage{ulem}
\usepackage{booktabs}
\usepackage{amsthm}
\usepackage{tikz}
\usepackage{pgfplots}
\usepackage[ruled,vlined]{algorithm2e}
\pgfplotsset{width=10cm,compat=1.9}
\geometry{a4paper,left=3cm,right=3cm,top=3cm,bottom=3cm}

\begin{document}
	\begin{center}
		{\heiti {\huge 第四次编程作业报告}}
	\end{center}
	
	\begin{center}
		{\large 求数2101\ 叶陈昊\ 3210106359}
	\end{center}
	
	\section{问题：硬币找零}
	有一定初始硬币数目的几种不同的美元硬币:$1,5,10,25$美分. 输入每种硬币的数量, 目标是找出使得总金额为$n$美分(也是输入) 的最小硬币数.
	
	请设计合理的测试用例, 并给出测试结果.  
	测试的重点应放在计算效率上, 并和你的理论分析结果做比较.
	
	\section{设计思路}
	\subsection{初步思路}
	一般地，设$c_0=1,c_1=5,c_2=10,c_3=25$，并分别设它们的数量为$n_0,n_1,n_2,n_3$.
	设总金额量为$n$. 设目标解为$\mathrm{dp}(n_0,n_1,n_2,n_3,n)$.
	
	若已知当
	$0\le m_0+m_1+m_2+m_3<n_0+n_1+n_2+n_3,\ 0\le m < n$时的目标值是
	$\mathrm{dp}(m_0,m_1,m_2,m_3,m)$，
	则动态规划的状态转移方程为：
	\begin{align}
		\mathrm{dp}(n_0,n_1,n_2,n_3,n)&=
		\min_{k: 0\le k\le 3, n_k\neq 0, n-c_k \ge 0}
		\mathrm{dp}(n_0-\delta_{0k},n_1-\delta_{1k},
		n_2-\delta_{2k},n_3-\delta_{3k},n-c_k)\nonumber\\
		&=\min\{\mathrm{dp}(n_0-1,n_1,n_2,n_3,n-c_0),
				\mathrm{dp}(n_0,n_1-1,n_2,n_3,n-c_1),\nonumber\\
			&	\mathrm{dp}(n_0,n_1,n_2-1,n_3,n-c_2),
				\mathrm{dp}(n_0,n_1,n_2,n_3-1,n-c_3)\}\label{idea}
	\end{align}

	其中式(\ref{idea})第二个等号右端项的每个dp中的元素均要大于等于0，若有一个小于0，
	则此dp的值默认为$+\infty$（为保证与求解最小值相容）.
	
	动态规划的边界条件有2种：
	\begin{align}
		\mathrm{dp}(n_0,n_1,n_2,n_3,0) &= 0,\ \forall n_j\ge 0, j=0,1,2,3;
		\label{dp(0)=0}\\
		\mathrm{dp}(n_0,n_1,n_2,n_3,k) &= +\infty,\ \forall n_j'\cdot c_j > k, 
		j=0,1,2,3,\ 
		1\le k\le n.\label{dp(k)=inf}
	\end{align}
	
	其中式(\ref{dp(0)=0})是因为总金额为0，不需要任何硬币拼凑，故目标值为0；
	在式(\ref{dp(k)=inf})中$n_j'=\min\{n_j,1\}(0\le j\le 3)$，这种情况是因为没有比总金额$k$小的硬币，只有比$k$大的硬币，导致解法不存在.
	为了与求最小值的目标相容，我们规定此时的目标值为$+\infty$.
	
	因此，如果用一个五维数组（规格为$ (n_0+1)\times(n_1+1)\times
	(n_2+1)\times(n_3+1)\times(n+1) $）去存储$\mathrm{dp}$中的值，理论上
	是可以通过边界条件自下而上算出目标值，但这种算法会略显笨拙，同时也会消耗
	大量的时空复杂度，在计算效率上大打折扣.因此，我们考虑一种相对能提高计算效率的方法.
	
	\subsection{思路改进}\label{thought}
	虽然不能暴力加数组的维度，但是我们可以加动态规划的次数.
	
	假设现在只有一种硬币（不妨设为$c_3$），现在我们考虑求解
	$\mathrm{dp}(0,0,0,n_3,j), 0\le j\le n.$（由于dp的前4个变量固定，
	我们将其写成$\mathrm{dp}[j].$）显然有边界条件
	$\mathrm{dp}[0]=0$，以及状态转移方程$\mathrm{dp}[j]=\min\{\mathrm{dp}
	[j-c_3]+1, \mathrm{dp}[j]\}(j\ge c_3)$.由此不难归纳出：
	\begin{align}
		\mathrm{dp}[j]=\min_{k:0\le k\le n_3, c_3k\le j}
		(\mathrm{dp}[j-c_3k]+k),\ 0\le j\le n.\label{case c3}
	\end{align}

	于是一种硬币的情形已经做完，现在来看两种硬币的情形（不妨设为$c_3,c_2$），
	考虑求解$\mathrm{dp}(0,0,n_2,n_3,j),0\le j\le n$.
	注意到当$n_2$取定时（即已确定用了多少枚10美分），只需要看$n_3$的值
	（即现在要花多少枚25美分）.此时情形化归为
	$\mathrm{dp}(0,0,0,n_3,j-c_2k)$（$k$为使用$c_2$硬币的数量，$0\le k\le n_2
	,c_2k\le j$），
	而此式的值在式(\ref{case c3})中已经给出.综上，得到新的dp值：
	\begin{align}
		\mathrm{dp}^{(1)}[j]=\min_{k:0\le k\le n_2, c_2k\le j}
		(\mathrm{dp}[j-c_2k]+k),\ 0\le j\le n.
	\end{align}

	那么，现在再加入硬币$c_1$，固定$n_1$，类似上述归纳，得到新的dp值
	（$\mathrm{dp}(0,n_1,n_2,n_3,j)$）：
	\begin{align}
		\mathrm{dp}^{(2)}[j]=\min_{k:0\le k\le n_1, c_1k\le j}
		(\mathrm{dp}^{(1)}[j-c_1k]+k),\ 0\le j\le n.
	\end{align}

	最后，加入硬币$c_0$，得到新的dp值（$\mathrm{dp}(n_0,n_1,n_2,n_3,j)$）：
	\begin{align}
		\mathrm{dp}^{(3)}[j]=\min_{k:0\le k\le n_0, c_0k\le j}
		(\mathrm{dp}^{(2)}[j-c_0k]+k),\ 0\le j\le n.
	\end{align}

	我们看到，题目所要求的即为
	$\mathrm{dp}(n_0,n_1,n_2,n_3,n)=\mathrm{dp}^{(3)}[n]$.
	
	\subsection{伪代码实现}
	由思路\ref{thought}，由于每次加入新硬币$c_i(0\le i\le 3)$时，
	我们需要更新整个dp的值，
	所以需要一个二维数组来保存上次的dp值，为了协调下标和代码实现，
	我们定义二维数组dp如下：
	$$ \mathrm{dp}\in \mathbb{Z}^{5\times(n+1)},
		\mathrm{dp}[4][0]=0, \mathrm{dp}[4][j]=+\infty(1\le j\le n).$$
	在这里，我们给这个数组的第5行dp[4]最先赋值（以实现自下而上的计算）.\ dp[4]中的元素是当最初一枚硬币都没有时，动态规划的目标值（即$\mathrm{dp}
	[4][j]=\mathrm{dp}(0,0,0,0,j),\ 0\le j\le n$）.
	
	接下来，根据\ref{thought}，对dp进行更新，更新后的dp存放在旧dp的上一行（
	即加入$c_3$后的dp放在数组第4行dp[3]，
	再加入$c_2$后更新的dp放在第3行dp[2]，以此类推）.根据这个思路，
	我们可以得到如下的伪代码，并获得结果为dp[0][$n$].
	
	\begin{algorithm}  
		\SetAlgoLined  
		%\KwData{dp array, n, n array, c array}  
		%\KwResult{Updated dp array}  
		\For{$i$ from 3 to 0}{  
			\For{$j$ from 0 to $n$}{  
				\For{$k$ satisfying $0\leq k\leq n_i$ and $c_i * k \leq j$}{  
					$\mathrm{dp}[i][j] = \min(\mathrm{dp}[i][j], \mathrm{dp}[i+1][j-c_{i} * k]+k)$\;  
				}  
			}  
		}  
		\caption{动态规划伪代码实现}  
	\end{algorithm}

	\subsection{理论效率计算}
	根据上述算法,时间复杂度主要取决于这个三重循环. 
	循环次数为：
	$$ \sum_{i=3}^{0}\sum_{j=0}^{n}\min\left\{n_i,\left\lfloor\frac{j}{c_i}
	\right\rfloor\right\}\leq \sum_{i=0}^{3}\sum_{j=0}^{n}n_i
	\leq \sum_{i=0}^{3}\sum_{j=0}^{n}N=4N(n+1).$$
	其中，$N:=\max_{0\le i\le 3}n_i$.
	从而忽略掉系数和相对小量，该算法的时间复杂度不超过$O(N\cdot n)$.
	
	空间复杂度主要取决于dp这个二维数组，由于$\mathrm{dp}\in \mathbb{Z}^{5\times(n+1)}$，因此该算法的空间复杂度为$O(n)$.
	
	\section{测试代码与分析}
	实现动态规划的函数详见\texttt{coin.h},
	测试代码详见\texttt{main.cpp}.其中测试了两个部分，一是输入普通的数据
	来检测输出是否符合题目要求，二是输入特定的数据来检验时间复杂度（即测试计算效率）.
	\subsection{测试数据与说明}
	测试数据及运行结果见\texttt{input.txt}、\texttt{output.txt}.
	下面给出一些数据具体的输入输出以及解释说明.
	（输入格式：$(n_0,n_1,n_2,n_3,n)$，输出格式：dp[0][$n$]）\\
	\begin{tabular}{ll}  
		1.& 输入：  1\ 2\ 3\ 4\ 0 \\  
		 &输出： 0 \\  
		 &解释： 总金额为0，需要0枚硬币. \\  
		2. &输入：  0\ 0\ 0\ 0\ 1 \\  
		 &输出： $-1$（注：程序中，结果若不存在，用$-1$表达） \\  
		 &解释： 总金额为1，没有硬币去凑到1，解法不存在. \\  
		3. &输入：  0\ 1\ 2\ 3\ 1 \\  
		&输出： $-1$ \\  
		&解释： 总金额为1，没有1金额的硬币，解法不存在. \\  
		4. &输入：  0\ 0\ 4\ 1\ 40 \\  
		&输出： $4$ \\  
		&解释： $4*10=40$,即用了4枚10美分的硬币. \\
		5. &输入：  5\ 2\ 3\ 5\ 99 \\  
		&输出： $9$ \\  
		&解释： $3*25+2*10+4*1=99$,即用了3枚25美分，2枚10美分，4枚1美分的硬币. \\
	\end{tabular} 

	\subsection{验证时间复杂度}
	接下来进行计算效率的测试. 由于本算法的时间复杂度为
	$O(N\cdot n)$， 我们不妨让4种硬币的个数都相同（即$n_i=N,0\le i\le 3$），
	利用控制变量法，分别扩增硬币个数$N$和总金额数$n$，观察程序的运行时间.
	
	进行了一次测试后，结果如下：\\
	\begin{tabular}{ll}  
		1.& 输入：  10\ 10\ 10\ 10\ 10 （注：$N\cdot n =10^2$） \\  
		&输出： 最小总硬币数: 1\quad 程序运行时间: 7微秒 \\    
		2.& 输入：  10\ 10\ 10\ 10\ 100 （注：$N\cdot n =10^3$）\\  
		&输出： 最小总硬币数: 4\quad 程序运行时间: 69微秒 \\
		3.& 输入：  100\ 100\ 100\ 100\ 100 （注：$N\cdot n =10^4$）\\  
		&输出： 最小总硬币数: 4\quad 程序运行时间: 135微秒 \\
		4.& 输入：  100\ 100\ 100\ 100\ 1000 （注：$N\cdot n =10^5$）\\  
		&输出： 最小总硬币数: 40\quad 程序运行时间: 3749微秒 \\   
		5.& 输入：  1000\ 1000\ 1000\ 1000\ 1000（注：$N\cdot n =10^6$） \\  
		&输出： 最小总硬币数: 40\quad 程序运行时间: 10663微秒 \\ 
		6.& 输入：  1000\ 1000\ 1000\ 1000\ 10000 （注：$N\cdot n =10^7$）\\  
		&输出： 最小总硬币数: 400\quad 程序运行时间: 454483微秒 \\ 
	\end{tabular} 
	
	由上述输出可以看出，每当$N\cdot n$扩大至原来的10倍（上升了一个数量级）后，
	输出也上升了一个数量级，这个结果大体符合我们的预期.
	
	
\end{document}